# -*- coding: utf-8 -*-
# author yzs
# date 2018-12-29

# 数学公式
# Description
# Implement pow(A, B) % C.In other words, given A, B and C, find (A^B)%C
# Input
# The first line of input consists number of the test cases. The following T lines consist of 3 numbers each
# separated by a space and in the following order:A B C
# 'A' being the base number, 'B' the exponent (power to the base number) and 'C' the modular.
# Constraints:1 ≤ T ≤ 70,1 ≤ A ≤ 10^5,1 ≤ B ≤ 10^5,1 ≤ C ≤ 10^5
# Output
# In each separate line print the modular exponent of the given numbers in the test case.
# Sample Input 1 
# 3
# 3 2 4
# 10 9 6
# 450 768 517
# Sample Output 1
# 1
# 4
# 34
# 快速幂算法


def power_mod(a, b, c):
    result = 1
    a = a % c
    while b > 0 :
        if b % 2 == 1:
            result = (result * a) % c
        b = b//2
        a = (a * a) % c
    print(result)


t = int(input().strip())
for i in range(t):
    data = list(map(int, input().strip().split()))
    a = data[0]
    b = data[1]
    c = data[2]
    power_mod(a, b, c)